package sort;

public class CountSort {
	public static void countSort(int[] array) {
		int max=array[0];
		int min=array[0];
		for(int x:array) {
			max=Math.max(max,x);
			min=Math.min(min,x);
		}
		
		int len=max-min+1;
		int[] count=new int[len];
		
		for(int x:array) {
			count[x-min]++;
		}
		
		for(int i=0,k=0;i<len;i++) {
			while(count[i]>0) {
				array[k++]=i+min;
				count[i]--;
			}
		}
	}
	
	public static void main(String[] args) {
		int[] arr=new int[]{3,5,9,7,2};
		countSort(arr);
		for(int x:arr) 
			System.out.print(x+" ");
	}
}
